1. Field of the Invention
The present invention relates to a variable-length code table and a coding device for converting equal-length data, and in particular to a variable-length code table which is used in image compression processing for performing variable-length coding in a table look-up system as well as a variable-length coding device using the same.
2. Description of the Background Art
Image information contains a great quantity of information. For example, one frame (1/30 seconds) of television image requires image information of a quantity corresponding to that of test data for one copy of a book. Further, real time transmission is required for the image data in many cases, and it is very difficult to transmit in real time such a great quantity of information.
Accordingly, such a technique is used that image data is compressed prior to actual transmission, and the compressed data is transmitted and is expanded at a receiver side. Since this can reduce the quantity of transmitted signals, a larger quantity of information can be transmitted in the same time period via the same transmission path. Therefore, signal compression technique is very important in the field of image processing.
As a method for the above, there has been a so-called variable-length coding processing, according to which short codes are assigned to bit patterns frequently appearing in the image data to be transmitted and relatively long codes are assigned to less frequently appearing bit patterns. FIG. 1 shows an example of an image data compression processing device using such a variable-length coding processing. This device has been proposed in Japanese Patent Application No. 5-60335 (1993) by the same assignee as the present application. In this example, there is shown a processing diagram of the image compression using the coding system specified by the MPEG standard.
Referring to FIG. 1, image data ID to be compressed is supplied to a DCT (Discrete Cosine Transform) processing device 202 via a subtracter 200 and a selector 218. DCT processing device 202 converts the input signal into frequency components. The signal processed by DCT processing device 202 is further quantized by a quantizer 204. The quantization relatively reduces the components at a high-frequency region of the data converted into frequency components by the DCT processing. This does not cause remarkable reduction of the image quality for human eyes, and thus is performed for reducing the quantity of data to be transmitted by removing high-frequency components.
The quantized data (i.e., run length data) is supplied to a variable-length coding unit 206 which performs variable-length coding on the data. The coded data is output as compressed image data VD via a buffer 208.
An output of quantizer 204 is also supplied to an inverse quantizer 210 and an inverse DCT processing unit 212. Inverse quantizer 210 and inverse DCT processing unit 212 are provided for predicting motion which will be described later. An output of inverse DCT processing unit 212 is also supplied to an adder 214.
Image data ID is also supplied to a motion predicting unit 216. Motion predicting unit 216 predicts, for example, the motion of image between frames and transmits information related only to the moving image for flattening data and allowing further compression so as to reduce the transmission quantity. The data after processing of prediction is supplied to adder 214.
The output data of adder 214 is supplied to subtracter 200 and motion predicting unit 216 via a selector 220. Owing to selecting operation of selectors 218 and 220, image compression is performed taking the prediction of motion into account.
FIG. 2 is a schematic block diagram of variable-length coding unit 206 shown in FIG. 1. Referring to FIG. 2, run length data of, e.g., 8 bits supplied from quantizer 204 in FIG. 1 is converted into run data and level data by a run length converter 236. These data are equal-length data. The level data represents the level of run length data other than 0. The run data represents the number of data of 0 following the data other than 0. As described before, the high frequency component contains many 0's owing to the DCT processing and quantization. Therefore, compression can be performed efficiently using the run length conversion. The run data and level data are supplied to a data RAM (Random Access Memory) 238 for run length data, and are supplied to a run length data to variable-length code converting unit 240 after being converted into the form of (run, level). Run length data to variable-length code converting unit 240 converts the (run, level) data into variable-length codes for supplying the same to a multiplexer 242. Run length data to variable-length code converting unit 240 will be detailed later.
Meanwhile, control information including compression method and data size is supplied to a data RAM 232 for a header. Data which is read from header data RAM 232 using the above control information as an address is supplied to a header producing unit 234. Header producing unit 234 and run length data to variable-length code converting unit 240 supply control signals to data RAM 232 for header and data RAM 238 for run length data, and thereby read data therefrom, respectively.
Header producing unit 234 outputs the header of data, and run length data to variable-length code converting unit 240 outputs variable-length-coded data. Multiplexer 242 selects the output of header producing unit 234 and the output of run length data to variable-length code converting unit 240 in accordance with a select signal sent from a whole control circuit 230, and supplies the same to an FIFO buffer 244.
FIFO buffer 244 buffers the output of multiplexer 242 in the FIFO manner in response to the control signals sent from header producing unit 234 and run length data to variable-length code converting unit 240, and outputs the same in response to an output request signal sent from a parallel/serial (P/S) interface 246. FIFO buffer 244 is provided for making adjustment between a processing speed of variable-length coding unit 206 and a speed of external output of data.
Parallel/serial interface 246 is responsive to the control signal sent from buffer 208 shown in FIG. 1 and supplies the data to buffer 208 in accordance with the same clock signal.
The whole control circuit 230 is provided for controlling various portions and units in variable-length coding unit 206 so as to multiplex the header information and the data on a time axis in accordance with the standard used in variable-length coding.
FIG. 3 schematically shows a structure of run length data to variable-length code converting unit 240. Referring to FIG. 3, run length data to variable-length code converting unit 240 includes a memory 250 storing a variable-length code table which is accessed using the run data and the level data as an address for outputting the corresponding variable-length code and its code length, a variable-length code generating circuit 252 for generating a variable-length code based on the data read from memory 250, and a control circuit 254 which controls reading from memory 250 and operation of variable-length code generating circuit 252 in accordance with the control signal sent from whole control circuit 230 (FIG. 2), while supplying control signals to neighboring circuits.
Referring to FIG. 4, the variable-length code table in memory 250 includes a plurality of variable-length code data 266 arranged at corresponding addresses. Each variable-length code table 266 includes a variable-length code region 268 of a 17-bit width storing variable-length codes corresponding to combination of given (run, level), and a code length region 270 of a 5-bit width storing information which specifies a length of the variable-length code stored in variable-length code region 268.
Address 260 for accessing variable-length code data 266 includes a run region 262 of 6 bits and a level region 264 of 7 bits, and thus includes 13 bits. The address is produced from the run data and level data supplied from the preceding stage as shown in FIG. 3, and variable-length code table memory 250 is accessed with the produced address for outputting the corresponding variable-length code data.
In address 260, 6 bits are allocated to run 262 and 7 bits are allocated to level 264 because a range of the run is from 0 to 63 and a range of the level is between .+-.41 so that 6 bits and 7 bits are required for representing them, respectively. FIGS. 5 to 10 show DCT output coefficient variable-length code tables of MPEG1. These tables shows all the major data.
As can be seen from FIGS. 5 to 10, the variable-length code region 268 is formed of 17 bits and code length region 270 is formed of 5 bits because the maximum length of the variable-length code is 17 bits. Code length region 270 is required because the code length is required even for handling the variable-length code and the code length of the variable-length code must be output together with the variable-length code.
Combinations of the run and level not mentioned in the tables in FIGS. 5 to 10 are processed by a coding unit (not shown) other than the above variable-length coding unit.
FIG. 11 is a block diagram showing the variable-length coding device using the conventional variable-length code table and also showing variable-length code table memory 250 and control circuit 254. Referring to FIG. 11, conventional variable-length coding device 252 includes a register 282, a 40-bit barrel shifter 104, a shift register 118 for outputting the variable-length code, a zero generating circuit 120, a register 108, 5-bit adder 112 and a code length register 114. Shift register 118 includes five 8-bit registers 118a-118e.
Control circuit 254 supplies control signals a, b, d, f and g to variable-length code table memory 250, register 108, register 282, variable-length register 114 and shift register 118 for operating them, respectively.
In the initial state, shift register 118 outputting the variable-length code and variable-length register 284 both have been cleared to 0. Forty-bit barrel shifter 104 is operable to shift the input data by a value indicated by code length register 114 and store the same in shift register 118.
Initially, the variable-length code and the code length in variable-length code table are stored in registers 282 and 114, respectively. It is assumed that the variable-length code thus stored is "001010" and the code length thus stored is "6". These values are supplied from registers 282 and 108 to 40-bit barrel shifter 104 and 5-bit adder 112, respectively.
The content of variable-length register 284 is 0. Therefore, 40-bit barrel shifter 104 passes the input data therethrough without shifting it, and supplies the input data to shift register 118 for code output.
Five-bit adder 112 adds the input data "6" and the content "0" of code length register 114 together, and writes the result "6" into the code length register 114. Code length register 114 is operable to supply a control signal h to shift register 118 for shifting the same and also supplies it as a data enable signal to a circuit at a subsequent stage, when the value stored in register 114 increases to or above 8. In this case, however, the content is "6", so that shift signal h is not output.
Then, it is assumed that a coded variable-length code of "00001000" is supplied to 40-bit barrel shifter 104 via register 282, and a code length "8" is supplied to the input of 5-bit adder 112 via register 108.
The content of code length register 114 is "6". Forty-bit barrel shifter 104, therefore, shifts the variable-length code by 6 bits to the right, and stores the same in shift register 118. At this time, the stored content of shift register 118 for outputting the code is formed of the initially supplied variable-length code stored at 6 bits starting from the highest bit. The currently supplied (i.e., second) variable-length code is stored at 7th and succeeding bits.
Five-bit adder 112 adds the input data "8" and the content "6" of code length register 114 together, and writes the result "14" into code length register 114.
Code length register 114 outputs shift signal h and equally divides its own content into eight, because the content has increased to 8 or more. Shift register 118 for outputting the code responds to shift signal h by shifting its contents by 8 bits to the left and outputting the content of shift register 118a as coded data (bit stream) from its left end. Thus, the content of 8-bit register 118a is output as the data, and the contents of registers 118b, 118c, 118d and 118e are transferred to registers 118a, 118b, 118c and 118d, respectively. Also, 0's of 8 bits are supplied and written into register 118e from zero generating circuit 120.
As a result of the above processing, the content of code length register 114 goes to "6". In this case, the content of code length register 114 represents the bit number of variable-length code "001000" stored in 8-bit register 118a. Thus, code length register 114 stores a data length of effective data stored in code outputting shift register 118.
When a next variable-length code is input, the input variable-length code is shifted to the right by a bit number of the variable-length code stored in 8-bit register 118a, and then is stored in shift register 112, so that shift register 118 for outputting code stores the next variable-length code at places immediately succeeding those of the variable-length code already stored in shift register 118.
The above processing is repetitively performed on the variable-length code and its code length sent from memory 250, and a variable-length code train is produced in the form of a bit stream.
The image compressing device in a related art flattens the data itself by predicting motion, and further performs the DCT processing and quantization for removing high-frequency components. Therefore, image signals to be compressed contains a large number of 0's, and can be compressed efficiently by using the variable-length code tables, e.g., shown in FIGS. 5 to 10. Since the table look-up system is used, complicated processing is not necessary, and fast coding processing can be performed.
However, the variable-length coding device using the table look-up system described above suffers from a disadvantage that a large memory is required. As can be seen from FIGS. 5 to 10, the variable-length codes have code lengths in a range from 2 to 17 bits. However, when preparing the variable-length code tables in the memory, it is difficult to set the length of variable-length code region itself to an arbitrary bit length, so that a field of a fixed length fitted to the maximum code length must be assigned to each variable-length code data. In order to represent one variable-length code, therefore, data of 22 bits (variable-length code of 17 bits and code length of 5 bits) is required. In order to develop this variable-length code table on the memory, it is necessary to provide a memory of at least 8 kilowords (address space of 13-bit address).times.22 bits.
In particular, the variable-length code tables shown in FIGS. 5 to 10 provide only two hundred-odd kinds of combinations of the run and level to be processed, but the space of 8 kilowords is required for developing the tables on the memory. Therefore, the variable-length coding processing has been desired that can utilize the memory space more efficiently and can reduce the required memory.
A proposal for achieving the above object is disclosed in Japanese Patent Laying-Open No. 4-142163 (1992). According to the disclosure of this publication, attention is paid to the fact that a certain repetition pattern (e.g., of "0") is often found at a leading portion of the variable-length code, and the variable-length code is converted into a number of repetition of the repetitive pattern starting from the leading end, the remaining data and the length of remaining data for storing the same. When accessing the memory, the variable-length code is produced by adding certain characters (e.g., 0's) equal in number to the repetition number of repetitive pattern to the leading end of the remaining data.
According to this manner, the repeated 0's starting from the leading end can be represented by a small number of bits. For example, 2 bits can represent the repetition number from 0 to 3, 3 bits can represent the repetition number from 0 to 7, and 4 bits can represent the repetition number from 0 to 15. This reduces the total bit length required for representing the variable-length code. Since the required bit length per address of memory is reduced, the whole capacity of memory can be reduced.
Even if this technique is used, however, a large unused region still remains in the memory. It is desired to utilize such a region efficiently. Further, the unused region must be utilized without losing convenience of the table look-up system.